package com.lans.HuffmanTree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

/**
 * @author: lans
 * @date: 2025/3/3
 * @name: 刘宇
 */
public class huffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 29, 6, 1};
        Node root = huffmanTree.createHuffmanTree(arr);
    }

    //创建哈夫曼树 并且把创建好的树返回回来
    public static Node createHuffmanTree(int[] array) {
        ArrayList<Node> nodes = new ArrayList<>();
        //1.把数据组每一个元素构建成节点
        for (int value : array) {
            //2.把构建好的每一个节点存放在集合中去
            nodes.add(new Node(value));
        }
        while (nodes.size()>1) {

            //3.从小到大进行排序操作
            Collections.sort(nodes);
            /**
             * 1.排序
             * 2.取出两个最小的节点组合成二叉树
             * 3.新的二叉树的权值是前两颗二叉树权值之和
             * 4.将这颗新的二叉树以根节点的权值大小再次排序
             */
            // 取出权值最小的两颗二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parentNode = new Node(leftNode.value + rightNode.value);
            parentNode.left = leftNode;
            parentNode.right = rightNode;
            //删除已构建的节点 放入新的节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parentNode);
        }
        return nodes.get(0);
    }
}